The present invention relates generally to computer architectures, and in particular to an architecture providing improved speed in traversing graph data.
A graph is a data structure describing a set of vertices (nodes) interconnected by edges to form a network. Graphs provide a useful model of many real-world structures, for example, relationships between webpages (where the vertices describe webpages and the edges describe links between webpages) or individuals in a social network (where the vertices describe individuals and the edges describe their friends or interests). Graphs are also used in the fields of neural networks and bioinformatics.
Computers are often called upon to process graph data by means of a “graph-traversal” operation where each vertex of the graph is visited and data is collected, for example, to produce a minimum spanning tree, or otherwise characterize the graph or the relationships of the vertices.
The vertices of a graph can be characterized according to “degree” indicating how many edges connect to that vertex. “Scale-free graphs” are a class of graphs where the distribution of vertex degrees follows a power-law distribution. Typically, such scale-free graphs have a small number of vertices with a large number of connections and many more vertices (a long-tale) with very few connections. During a graph-traversal, such scale-free graphs produce large numbers of redundant edge checks (investigating vertices that have already been visited). These edge checks require inefficient, irregular access to the memory holding the graph data.
Improved efficiency in graph-traversal can been accomplished through the use of a hybrid traversal strategy employing a “top-down” traversal followed by a “bottom-up” traversal. In an example top-down traversal (in this case a breadth-first search), a conventional CPU or GPU-based system executes the program to review the graph data outward from a starting vertex to find its neighbors (edges leading to other vertices) which establish a frontier. The vertices in this frontier are marked as visited and then edges from these vertices investigated in turn to establish a new frontier. When after multiple iterations the frontier has reached a critical size, the search strategy shifts to a “bottom-up” traversal. In this mode, the computer looks at the remaining un-visited vertices to check to see if they have a connection to the existing frontier. If so, that vertex is marked as visited and added to the frontier and the strategy immediately stops searching the other edges of that vertex, greatly saving processing time.
The top-down and bottom-up search strategies can be both executed using parallel processors; however, the “top-down” traversal requires an atomic updating of the frontier. This atomic updating is not required for the bottom-up strategy which investigates each vertex separately.
A description of this hybrid search strategy is found, for example, in Scott Beamer, Aydin Buluc, Krste Asanovic, and David Patterson, 2013, distributed memory breadth-first search revisited: Enabling Bottom-Up Search, in Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), 2013 IEEE 27th International, IEEE, 1618-1627 (the Beamer reference) hereby incorporated by reference.
Graph data structures can quickly become large making graph-traversal slow even with such hybrid search strategies. Currently, the social networking site of Facebook is described by a graph with over 1 billion vertices and more than 1 trillion edges.